package leetcode_901_1000;

import java.util.ArrayList;
import java.util.List;

public class LeeCode_995 {
    public static void main(String[] args) {
        System.out.println(minKBitFlips(new int[]{0, 1, 0}, 1));
        System.out.println(minKBitFlips(new int[]{0,0,0,1,0,1,1,0}, 3));
    }
    private static int minKBitFlips(int[] nums, int k) {
        int n = nums.length;
        int i = 0, ans = 0;
        List<Integer> list = new ArrayList<>();
        int[] plus = new int[n];
        int index = -1;
        while (i < n){
            while (!list.isEmpty() && index < list.size() && list.get(index) < i){
                index++;
            }
            if (!list.isEmpty() && index < list.size() && list.get(index) >= i){
                plus[i] += list.size() - index;
            }
            if ((nums[i] == 0 && (plus[i] & 1) == 0) || (nums[i] == 1 && (plus[i] & 1) == 1)){
                list.add(i + k - 1);
                if (index == -1)
                    index = 0;
                if (i + k - 1 >= n)
                    return -1;
                ans++;
            }
            i++;
        }
        return ans;
    }
}